package my.jwds.p720;

import com.alibaba.fastjson.JSON;

import java.util.HashMap;
import java.util.Map;

public class LongestWord {

    public static void main(String[] args) {

        LongestWord obj = new LongestWord();
        String [] words = JSON.parseObject("[\"a\",\"banana\",\"app\",\"appl\",\"ap\",\"apply\",\"apple\"]",String[].class);
        long start = System.currentTimeMillis();
        System.out.println(obj.longestWord(words));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    public String longestWord(String[] words) {
        Map<String,Boolean> map = new HashMap<>();
        for (String word : words) {
            if (word.length() == 1){
                map.put(word,true);
            }else{
                map.put(word,null);
            }

        }
        int max = 0;
        String res = null;
        for (String word : words) {
            Boolean bool = isEvolutive(word,map);
            if (bool){
                if (word.length() > max){
                    max = word.length();
                    res = word;
                }else if (word.length() == max && res.compareTo(word) > 0){
                    res = word;
                }

            }
        }
        return res;
    }

    Boolean isEvolutive(String word,Map<String,Boolean> map){
        if (!map.containsKey(word)){
            return false;
        }
        Boolean bool = map.get(word);
        if (bool != null)return bool;
        bool = isEvolutive(word.substring(0,word.length()-1),map);
        map.put(word,bool);
        return bool;
    }
}